[POJ 2686] Traveling by Stagecoach

原题链接:[POJ 2686] Traveling by Stagecoach
原题大意:有$m$个城市,$n$张票.给定了起点和终点,以及两个城市之间的距离,假如两个城市之间是联通的,那么在使用一张车票的时候,会有$t_i$只马的车载你到另一个城市,需要的时间是距离除马的数量.每张车票只能用一次现求从起点到终点最少时间是多少.
数据范围:
$1 \leq n \leq 8$
$2 \leq m \leq 30$

思路

由于数据量很小,在这种情况下考虑到指数级的算法可能的就是搜索和状压$DP$.这个题如果去掉车票的限制就是一个普通的最短路问题.如果要加入这个车票的限制,则在递推的时候也要把整个车票的状态全考虑进去,因此这就比较明显是一个状态压缩的形式:把所有的车票用二进制数压缩,$1$表示用了,将整个状态丢进去考虑再求最短路即可.
不过这题还有一个性质:可以发现从起点一直往外拓展的话,整个车票集合是只增不减的,也就是说如果把状态看成点,转移看成边,那么整个图是一个$DAG$,即可以直接$DP$递推得到最后的答案.

状态设计

状态:$$f[S][v]$表示当前手上的车票集合是$S$,人在$v$城市时最少要消耗多少时间,集合里如果是$1$表示已经用了,$0$表示没有用.
入口:$f[0][a]=0$一开始在$a$城市,自然为$0$.由于要求最小值,因此其他为正无穷.
出口:$min{f[~][b]}$其中~表示任意的值,即只要能到$v$即可.
转移:首先遍历起点$v$,再遍历集合里每个元素,看哪个车票还没用,记为$i$.再枚举谁是下一个到达的城市$u$.这个过程就是从$v$到$u$使用$i$号车票.则实际产生的代价就是$dist[v][u] / t[i]$.而后一个状态,也即是用掉了$i$车票的状态记作$S' = S | (1 << i)$.表达式为$f[S'][u] = min(f[S'][u],f[S][v] + dist[v][u] / t)$

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;

int n,m,p,S,T;
const int N = 100,M = 10000,_N = 1 << 8;
const double INF = 1e12;
int dist[N][N];
double f[_N][N];
int t[N];
int main()
{
	while((scanf("%d%d%d%d%d",&n,&m,&p,&S,&T) == 5))
	{
		if(!n && !m && !p && !S && !T)	break;
		--S;--T;
		for(int i = 0;i < n;++i)	scanf("%d",&t[i]);
		for(int i = 0;i < 1 << n;++i)	fill(f[i],f[i] + m,INF);		
		for(int i = 0;i < m;++i)	fill(dist[i],dist[i] + m,-1);
		for(int i = 0;i < p;++i)
		{
			int u,v,w;scanf("%d%d%d",&u,&v,&w);
			--u;--v;
			dist[u][v] = dist[v][u] = w;
		}
		f[0][S] = 0;
		double res = INF;
		for(int state = 0;state < 1 << n;++state)
		{
			for(int v = 0;v < m;++v)
			{
				for(int i = 0;i < n;++i)
				{
					if(!(state >> i & 1))
					{
						for(int u = 0;u < m;++u)
						{
							if(dist[v][u] >= 0)
							{
								double rc = (double)dist[v][u] / t[i];
								int _state = state | (1 << i);
								f[_state][u] = min(f[_state][u],f[state][v] + rc);
							}
						}
					}
				}
			}
			res = min(res,f[state][T]);
		}
		if(res == INF)	printf("Impossible\n");
		else printf("%.3lf\n",res);
	}
    return 0;
}